package Algorithm.handleString;

/**
 * 67. 二进制求和 https://leetcode.cn/problems/add-binary
 * 题目简述：给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
 */
public class AddBinary {

    /**
     * 思路：从末尾进行遍历计算，较短的遍历完后直接补0继续遍历，直到两个字符串都遍历完毕。
     * 每次计算即三个位（包括进位）相加和sum，当前为结果为sum & 1，新的进位为sum右移一位。
     * 遍历完后看是否还要再加一个进位
     */
    public String addBinary(String a, String b) {
        int i = a.length()-1, j = b.length()-1;
        int x = 0;
        StringBuilder sb = new StringBuilder();
        while (i >= 0 || j >= 0) { //注意看补0方式
            int sum = x;
            sum += i >= 0 ? a.charAt(i--) - '0' : 0;
            sum += j >= 0 ? b.charAt(j--) - '0' : 0;
            sb.append(sum & 1); //通过与运算对2取余
            x = sum >> 1; //通过移位运算取进位
        }
        if (x == 1) sb.append('1');
        return sb.reverse().toString();
    }
}
